Libris Britannia 4/science library(b).zip/science library(b)/DDJMAG/DDJ9212.ZIP/splay.asc

Text File | 1992-11-30 | 6KB | 270 lines

_SPLAY TREES_
by Dean Clark

[LISTING ONE]

void zig_left(TREENODE *t)
{
    TREENODE    *p, *r;
    p = t->parent;
    r = t->right;
    t->right = p;
    if (r) {
        r->parent = p;
        }
    p->left = r;
    p->parent = t;
}
void zig_right(TREENODE *t)
{
    TREENODE    *p, *l;
    l = t->left;
    p = t->parent;
    p->right = t;
    if (l) {
        l->parent = t;
    }
    p->right = l;
    p->parent = t;
}
void zig_zig_left(TREENODE *t)
{
    TREENODE    *p, *pr, *g, *r, *gp;
    p = t->parent;
    g = p->parent;
    gp = g->parent;
    r = t->right;
    pr = p->right;
    p->right = g;
    g->left = pr;
    t->parent = gp;
    t->right = p;
    p->left = r;
    if (r) {
        r->parent = p;
    }
    if (pr) {
        pr->parent = g;
    }
    if (gp) {
        if (gp->left == g) {
            gp->left = t;
        }
        else {
            gp->right = t;
        }
    }
}
void zig_zig_right(TREENODE *t)
{
    TREENODE    *p, *pl, *g, *l, *gp;
    p = t->parent;
    g = p->parent;
    gp = g->parent;
    l = t->left;
    pl = p->left;
    p->left = g;
    g->right = pl;
    t->parent = gp;
    t->left = p;
    p->right = l;
    if (l) {
        l->parent = p;
    }
    if (pl) {
        pl->parent = g;
    }
    if (gp) {
        if (gp->left == g) {
            gp->left = t;
        }
        else {
            gp->right = t;
        }
    }
}
void zig_zag_left(TREENODE *t)
{
    TREENODE    *p, *gp, *ggp, *l, *r;
    p = t->parent;
    gp = p->parent;
    ggp = gp->parent;
    l = t->left;
    r = t->right;
    t->parent = ggp;
    t->left = p;
    t->right = gp;
    gp->parent = t;
    p->parent = t;
    p->right = l;
    gp->left = r;
    if (l) {
        l->parent = p;
    }
    if (r) {
        r->parent = gp;
    }
    if (ggp) {
        if (ggp->left == gp) {
            ggp->left = t;
        }
        else {
            ggp->right = t;
        }
    }
}
void zig_zag_right(TREENODE *t)
{
    TREENODE    *p, *gp, *ggp, *l, *r;
    p = t->parent;
    gp = p->parent;
    ggp = gp->parent;
    l = t->left;
    r = t->right;
    t->left = gp;
    t->right = p;
    t->parent = ggp;
    p->parent = t;
    gp->parent = t;
    gp->right = l;
    p->left = r;
    if (l) {
        l->parent = gp;
    }
    if (r) {
        r->parent = p;
    }
    if (ggp) {
        if (ggp->left == gp) {
            ggp->left = t;
        }
        else {
            ggp->right = t;
        }
    }
}


[LISTING TWO]

/* Splay functions
**  Assumptions: Tree is pointed to by global variable T,
**   type KEYTYPE
**     External function Compare_Key(KEYTYPE k1, KEYTYPE k2) returns
**         0 if the two keys are equal, -1 if first key is less than
**         second, 1 if first is greater than second
**     External rotation functions from listing 1
*/

Splay(KEYTYPE k)
{
    int gle;
    /* Assume global tree T.  Traverse T looking for key.  Compare_Key()
    ** returns 0 if the two keys are equal, -1 if the first is less than
    ** the second, 1 if first is greater than the second */
    while ((gle = Compare_Key(T->key,k)) != 0) {
        if (gle > 0) {
            if (T->left) {
                T = T->left;
            }
            else break;
        }
        else {
            if (T->right) {
                T = T->right;
            }
            else break;
        }
    }
    /* T now points to the node containing the key k, or to the inorder
    ** successor or predecessor to k. We don't really care which at
    ** this point. T will be root when its parent pointer points to itself */
    while (T->parent != T) {
        if (T->parent->parent) {
            /* zig-zig or zig-zag*/
            if (T->parent->parent->left == T->parent) {
                if (T->parent->left == T) {
                    zig_zig_left(T);
                }
                else {
                    zig_zag_left(T);
                }
            }
            else {
                if (T->parent->right == T) {
                    zig_zig_right(T);
                }
                else {
                    zig_zag_right(T);
                }
            }
        }
        else {
            /* zig */
            if (T->parent->left == T) {
                zig_left(T);
            }
            else {
                zig_right(T);
            }
        }
    }
}



[LISTING THREE]

/* Splay Tree Standard Operations -- Find, Delete and Insert functions for
**   splay trees. Assumptions:
**     Tree is pointed to by global variable T, type KEYTYPE
**     External function Compare_Key(KEYTYPE k1, KEYTYPE k2) returns
**         0 if the two keys are equal, -1 if first key is less than
**         second, 1 if first is greater than second
**     External function Destroy_Key(KEYTYPE k) that recovers memory
**         used by a key
**     Special KEYTYPE variable ERROR_KEY used as an error sentinel
*/

KEYTYPE Find(KEYTYPE k)
{
    Splay(k);
    /* If k was in the tree it's now the root node */
    if (T->key == k) {
        return (T->key);
    }
    else {
        return (ERROR_KEY);
    }
}
void Delete(KEYTYPE k)
{
    TREENODE    *l, *r;
    /* Bring target node to the root */
    Splay(k);
    /* Make sure key was in the tree... */
    if (Compare_Key(T->key, k) == 0) {
        /* Detach the node and dispose of it */
        l = T->left;
        r = T->right;
        Destroy_Node(T);
        /* Splay left subtree to find the new root of tree (see text) */
        T = l;
        Splay(k);
        /* Root and left subtree are fine now, just attach right subtree */
        T->right = r;
    }
}
void Insert(KEYTYPE k)
{
    TREENODE    *x;
    /* Insert the new node into the tree */
    Attach_Node(k);
    /* Now Splay to bring the new node to root. This is somewhat inefficient
    ** because Splay searches the tree all over again. */
    Splay(k);
}